/*
 * CCVisu is a tool for visual graph clustering
 * and general force-directed graph layout.
 * This file is part of CCVisu.
 *
 * Copyright (C) 2005-2011  Dirk Beyer
 *
 * CCVisu is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * CCVisu is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with CCVisu; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Please find the GNU Lesser General Public License in file
 * license_lgpl.txt or http://www.gnu.org/licenses/lgpl.txt
 *
 * Dirk Beyer    (firstname.lastname@uni-passau.de)
 * University of Passau, Bavaria, Germany
 */
package org.sosy_lab.ccvisu.measuring;

import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

import org.sosy_lab.ccvisu.graph.GraphData;
import org.sosy_lab.ccvisu.graph.GraphEdge;
import org.sosy_lab.ccvisu.graph.GraphVertex;
import org.sosy_lab.ccvisu.graph.Group;
import org.sosy_lab.ccvisu.graph.Position;
import org.sosy_lab.ccvisu.graph.RadiusOfGroup;


public class FeatureDependency {
  private static Map<GraphVertex, LinkedList<GraphVertex>> connectedVertices = new HashMap<GraphVertex, LinkedList<GraphVertex>>();

  /**
   * Calculate the Internal-ratio Feature Dependency (IFD)
   * as described by Apel and Beyer
   * in "Feature Cohesion in Software Product Lines: An Exploratory Study"
   */
  public static int calculateIFD(Group featureGroup, GraphData graph) {
    int refCount = 0, iec = 100;
    float sum = 0.0f;
    for(GraphVertex elementVertex : featureGroup.getNodes()) {
      for(GraphEdge e : graph.getAdjacent(elementVertex, ".*")) {
        //if((e.getU() != e.getV()) && featureGroup.getNodes().contains(e.getU()) && featureGroup.getNodes().contains(e.getV())) {
        if (featureGroup.getNodes().contains(e.getSource()) && featureGroup.getNodes().contains(e.getTarget())) {
          refCount++;
        }
      }
      //sum += ((float)refCount) / ((float)(featureGroup.getNodes().size() - 1));
      sum += ((float) refCount) / (float) featureGroup.getNodes().size();
      refCount = 0;
    }

    if(featureGroup.getNodes().size() > 1) {
      iec = Math.round(100.0f * (sum / (featureGroup.getNodes().size())));
    }
    return iec;
  }

  /**
   * Calculate the Distance-based Internal-ratio Feature Dependency (IFD_W)
   * as described by Apel and Beyer
   * in "Feature Cohesion in Software Product Lines: An Exploratory Study"
   */
  public static int calculateIFD_W(Group featureGroup, GraphData graph) {
    int iec = 100;
    float refValue = 0.0f, sum = 0.0f;
    for(GraphVertex elementVertex : featureGroup.getNodes()) {

      LinkedList<GraphVertex> connectedVertices = getConnectedVertices(elementVertex, ".*", graph);
      Position minPos = Position.min(connectedVertices, false);
      Position maxPos = Position.max(connectedVertices, false);
      float diagonal = minPos.distanceTo(maxPos);

      for(GraphEdge e : graph.getAdjacent(elementVertex, ".*")) {
        //if((e.getU() != e.getV()) && featureGroup.getNodes().contains(e.getU()) && featureGroup.getNodes().contains(e.getV())) {
        if(featureGroup.getNodes().contains(e.getSource()) && featureGroup.getNodes().contains(e.getTarget())) {
          refValue = refValue + (1.0f - (e.getLength() / diagonal));
        }
      }
      //sum += refValue / ((float)(featureGroup.getNodes().size() - 1));
      sum += refValue / featureGroup.getNodes().size();
      refValue = 0.0f;
    }

    if(featureGroup.getNodes().size() > 1) {
      iec = Math.round(100.0f * (sum / (featureGroup.getNodes().size())));
    }
    return iec;
  }

  /**
   * Calculate the External-ratio Feature Dependency (EFD)
   * as described by Apel and Beyer
   * in "Feature Cohesion in Software Product Lines: An Exploratory Study"
   */
  public static int calculateEFD(Group featureGroup, GraphData graph) {
    int countInner = 0, countOuter = 0, ifc = 100;
    for(GraphVertex elementVertex : featureGroup) {
      for (GraphEdge e : graph.getAdjacent(elementVertex, ".*")) {
        if(!featureGroup.getNodes().contains(e.getSource()) || !featureGroup.getNodes().contains(e.getTarget())) {
          countOuter++;
        } else {
          countInner++;
        }
      }
    }
    if((countInner + countOuter) > 0) {
      ifc = Math.round(100.0f * ((float)countInner / (float)(countInner + countOuter)));
    }
    return ifc;
  }

  /**
   * Calculate the Distance-based External-ratio Feature Dependency (EFD_W)
   * as described by Apel and Beyer
   * in "Feature Cohesion in Software Product Lines: An Exploratory Study"
   */
  public static int calculateEFD_W(Group featureGroup, GraphData graph) {
    int innerCount = 0, outerCount = 0, ifc = 100;
    float innerValue = 0.0f, outerValue = 0.0f;

    for(GraphVertex elementVertex : featureGroup) {

      LinkedList<GraphVertex> connectedVertices = getConnectedVertices(elementVertex, ".*", graph);
      Position minPos = Position.min(connectedVertices, false);
      Position maxPos = Position.max(connectedVertices, false);
      float diagonal = minPos.distanceTo(maxPos);

      for (GraphEdge e : graph.getAdjacent(elementVertex, ".*")) {
        if(!featureGroup.getNodes().contains(e.getSource()) || !featureGroup.getNodes().contains(e.getTarget())) {
          outerValue = outerValue + (1.0f - (e.getLength() / diagonal));
          outerCount++;
        } else if(e.getSource() == e.getTarget()) {
          innerValue = innerValue + 1.0f;
          innerCount++;
        } else {
          innerValue = innerValue + (1.0f - (e.getLength() / diagonal));
          innerCount++;
        }
      }
    }

    if((innerCount + outerCount) > 0) {
      ifc = Math.round(100.0f * (innerValue / (innerValue + outerValue)));
    }
    return ifc;
  }


  /**
   * Calculate the average radius.
   *
   * @param featureGroup
   * @param graph
   * @return
   */
  public static int calculateAR(Group featureGroup, GraphData graph) {

    if(featureGroup.getNodes().size() == 0) {
      return 100;
    } else {
      return averageRadius(featureGroup, graph);
    }
  }

  public static int calculateMR(Group featureGroup, GraphData graph) {

    if(featureGroup.getNodes().size() == 0) {
      return 100;
    } else {
      return maximumRadius(featureGroup, graph);
    }
  }

  private static int averageRadius(Group featureGroup, GraphData graph) {

    int numAR = 0;
    int sumAR = 0;
    LinkedList<GraphVertex> visitedNodes = new LinkedList<GraphVertex>();

    for(GraphVertex cur : featureGroup.getNodes()) {
      LinkedList<GraphVertex> connectedNodes = getConnectedVertices(cur, ".*", graph);
      LinkedList<GraphVertex> connectedFeatureNodes = new LinkedList<GraphVertex>();
      for(GraphVertex aux : connectedNodes) {
        if(featureGroup.getNodes().contains(aux)) {
          connectedFeatureNodes.add(aux);
        }
      }

      if(!visitedNodes.contains(cur)) {
        if(connectedFeatureNodes.size() > 1) {
          int nbr = connectedFeatureNodes.size();
          Position baryCenter = new Position();
          for (GraphVertex lCurrVertex : connectedFeatureNodes) {
            baryCenter.add(lCurrVertex.getPosition());
          }
          baryCenter.div(nbr);

          float averageRadius = 0;
          for (GraphVertex v : connectedFeatureNodes) {
            float radius = v.distanceTo(baryCenter);
            averageRadius += radius;
          }
          averageRadius /= nbr;

          Position minPos = Position.min(connectedNodes, false);
          Position maxPos = Position.max(connectedNodes, false);
          float diagonal = minPos.distanceTo(maxPos);

          sumAR += Math.round(100.0f * (1.0f - (averageRadius / diagonal)));
          numAR++;
          visitedNodes.addAll(connectedFeatureNodes);
        } else {
          sumAR += 100;
          numAR++;
        }
      }
    }

    return Math.round(sumAR / numAR);
  }

  private static int maximumRadius(Group featureGroup, GraphData graph) {

    int numMR = 0;
    int sumMR = 0;
    LinkedList<GraphVertex> visitedNodes = new LinkedList<GraphVertex>();

    for(GraphVertex cur : featureGroup.getNodes()) {
      LinkedList<GraphVertex> connectedNodes = getConnectedVertices(cur, ".*", graph);
      LinkedList<GraphVertex> connectedFeatureNodes = new LinkedList<GraphVertex>();
      for(GraphVertex aux : connectedNodes) {
        if(featureGroup.getNodes().contains(aux)) {
          connectedFeatureNodes.add(aux);
        }
      }

      if(!visitedNodes.contains(cur)) {
        if(connectedFeatureNodes.size() > 1) {
          int nbr = connectedFeatureNodes.size();
          Position baryCenter = new Position();
          for (GraphVertex lCurrVertex : connectedFeatureNodes) {
            baryCenter.add(lCurrVertex.getPosition());
          }
          baryCenter.div(nbr);

          float maxRadius = 0;
          for (GraphVertex v : connectedFeatureNodes) {
            float radius = v.distanceTo(baryCenter);
            maxRadius = Math.max(maxRadius, radius);
          }

          Position minPos = Position.min(connectedNodes, false);
          Position maxPos = Position.max(connectedNodes, false);
          float diagonal = minPos.distanceTo(maxPos);

          sumMR += Math.round(100.0f * (1.0f - (maxRadius / diagonal)));
          numMR++;
          visitedNodes.addAll(connectedFeatureNodes);
        } else {
          sumMR += 100;
          numMR++;
        }
      }
    }

    return Math.round(sumMR / numMR);
  }


  private static LinkedList<GraphVertex> getConnectedVertices(GraphVertex current, String relName, GraphData graph) {
    if(connectedVertices.containsKey(current)) {
      return connectedVertices.get(current);
    } else {
      LinkedList<GraphVertex> res = new LinkedList<GraphVertex>();
      getConnectedVerticesInner(current, relName, res, graph);
      return res;
    }
  }

  private static void getConnectedVerticesInner(GraphVertex current, String relName, LinkedList<GraphVertex> res, GraphData graph) {
    res.add(current);
    connectedVertices.put(current, res);
    for(GraphEdge edge : graph.getAdjacentUndirected(current, relName)) {
      if(edge.getSource() == current && !res.contains(edge.getTarget())) {
        getConnectedVerticesInner(edge.getTarget(), relName, res, graph);
      } else if(edge.getTarget() == current && !res.contains(edge.getSource())) {
        getConnectedVerticesInner(edge.getSource(), relName, res, graph);
      }
    }
  }

  private static boolean belongsToFeature(GraphVertex element, GraphVertex feature, GraphData graph) {
    boolean res = false;
    Collection<GraphEdge> adjacentEdgeList = graph.getAdjacent(feature, "Introduces");
    for (GraphEdge adjEdge : adjacentEdgeList) {
      if(adjEdge.getTarget() == element || adjEdge.getSource() == element) {
        res = true;
      }
    }
    return res;
  }

  /////////////////////////////////////////////////////////////////////////////////////
  // old measures (not included in the paper)
  /////////////////////////////////////////////////////////////////////////////////////
  public static int pdPlainWeighted(Group featureGroup, GraphData graph) {
    int count = 0;
    float value = 0.0f;

    for(GraphVertex elementVertex : featureGroup) {
      LinkedList<GraphVertex> connectedVertices = getConnectedVertices(elementVertex, ".*", graph);
      Position minPos = Position.min(connectedVertices, false);
      Position maxPos = Position.max(connectedVertices, false);
      float diagonal = minPos.distanceTo(maxPos);
      for (GraphEdge e : graph.getAdjacent(elementVertex, ".*")) {
        if(featureGroup.getNodes().contains(e.getSource()) && featureGroup.getNodes().contains(e.getTarget())) {
          if(e.getSource() == e.getTarget()) {
            value = value + 1.0f;
          } else {
            value = value + (1.0f - (e.getLength() / diagonal));
          }
          count++;
        }
      }
    }

    if(count > 0) {
      return Math.round(100.0f * (value / count));
    } else {
      return 100;
    }
  }

  public static int iecExtended(GraphVertex featureVertex, GraphData graph) {
    int refCount = 0, iec = 100;
    float sum = 0.0f;
    int num = graph.getAdjacent(featureVertex, "Introduces").size();
    for(GraphEdge intrEdge : graph.getAdjacent(featureVertex, "Introduces")) {
      GraphVertex elementVertex;
      if(intrEdge.getSource() == featureVertex) {
        elementVertex = intrEdge.getTarget();
      } else {
        elementVertex = intrEdge.getSource();
      }
      for(GraphEdge e : graph.getAdjacent(elementVertex, ".*")) {
        if((e.getSource() != e.getTarget())
            && belongsToFeature(e.getSource(), featureVertex, graph)
            && belongsToFeature(e.getTarget(), featureVertex, graph)) {
          refCount++;
        }
      }
      sum += ((float)refCount) / ((float)(num - 1));
      refCount = 0;
    }
    if(num > 1) {
      iec = Math.round(100.0f * (sum / num));
    }
    return iec;
  }

  public static int iecExtendedWeighted(GraphVertex featureVertex, GraphData graph) {
    int iec = 100;
    float refValue = 0.0f, sum = 0.0f;
    int num = graph.getAdjacent(featureVertex, "Introduces").size();
    for(GraphEdge intrEdge : graph.getAdjacent(featureVertex, "Introduces")) {
      GraphVertex elementVertex;
      if(intrEdge.getSource() == featureVertex) {
        elementVertex = intrEdge.getTarget();
      } else {
        elementVertex = intrEdge.getSource();
      }

      LinkedList<GraphVertex> connectedVertices = getConnectedVertices(elementVertex, ".*", graph);
      Position minPos = Position.min(connectedVertices, false);
      Position maxPos = Position.max(connectedVertices, false);
      float diagonal = minPos.distanceTo(maxPos);

      for(GraphEdge e : graph.getAdjacent(elementVertex, ".*")) {
        if((e.getSource() != e.getTarget())
            && belongsToFeature(e.getSource(), featureVertex, graph)
            && belongsToFeature(e.getTarget(), featureVertex, graph)) {

          refValue = refValue + (1.0f - (e.getLength() / diagonal));
        }
      }
      sum += (refValue) / ((num - 1));
      refValue = 0;
    }
    if(num > 1) {
      iec = Math.round(100.0f * (sum / num));
    }
    return iec;
  }

  public static int ifcExtended(GraphVertex featureVertex, GraphData graph) {
    int countInner = 0, countOuter = 0, ifc = 100;
    for(GraphEdge intrEdge : graph.getAdjacent(featureVertex, "Introduces")) {
      GraphVertex elementVertex;
      if(intrEdge.getSource() == featureVertex) {
        elementVertex = intrEdge.getTarget();
      } else {
        elementVertex = intrEdge.getSource();
      }
      for (GraphEdge e : graph.getAdjacent(elementVertex, ".*")) {
        if(!e.getRelationName().equals("Introduces")) {
          if(!belongsToFeature(e.getSource(), featureVertex, graph)
              || !belongsToFeature(e.getTarget(), featureVertex, graph)) {
            countOuter++;
          } else {
            countInner++;
          }
        }
      }
    }
    if((countInner + countOuter) > 0) {
      ifc = Math.round(100.0f * ((float)countInner / (float)(countInner + countOuter)));
    }
    return ifc;
  }

  public static int ifcExtendedWeighted(GraphVertex featureVertex, GraphData graph) {
    int innerCount = 0, outerCount = 0, ifc = 100;
    float innerValue = 0.0f, outerValue = 0.0f;

    for(GraphEdge intrEdge : graph.getAdjacent(featureVertex, "Introduces")) {
      GraphVertex elementVertex;
      if(intrEdge.getSource() == featureVertex) {
        elementVertex = intrEdge.getTarget();
      } else {
        elementVertex = intrEdge.getSource();
      }

      LinkedList<GraphVertex> connectedVertices = getConnectedVertices(elementVertex, ".*", graph);
      Position minPos = Position.min(connectedVertices, false);
      Position maxPos = Position.max(connectedVertices, false);
      float diagonal = minPos.distanceTo(maxPos);

      for (GraphEdge e : graph.getAdjacent(elementVertex, ".*")) {
        if(!e.getRelationName().equals("Introduces")) {
          if(!belongsToFeature(e.getSource(), featureVertex, graph)
              || !belongsToFeature(e.getTarget(), featureVertex, graph)) {
            outerValue = outerValue + (1.0f - (e.getLength() / diagonal));
            outerCount++;

          } else if(e.getSource() == e.getTarget()) {
            innerValue = innerValue + 1.0f;
            innerCount++;

          } else {
            innerValue = innerValue + (1.0f - (e.getLength() / diagonal));
            innerCount++;
          }
        }
      }
    }
    if((innerCount + outerCount) > 0) {
      ifc = Math.round(100.0f * (innerValue / (innerValue + outerValue)));
    }
    return ifc;
  }

  public static int pdExtendedWeighted(GraphVertex featureVertex, GraphData graph) {
    int count = 0;
    float value = 0.0f;
    for(GraphEdge intrEdge : graph.getAdjacent(featureVertex, "Introduces")) {
      GraphVertex elementVertex;
      if(intrEdge.getSource() == featureVertex) {
        elementVertex = intrEdge.getTarget();
      } else {
        elementVertex = intrEdge.getSource();
      }

      LinkedList<GraphVertex> connectedVertices = getConnectedVertices(elementVertex, ".*", graph);
      Position minPos = Position.min(connectedVertices, false);
      Position maxPos = Position.max(connectedVertices, false);
      float diagonal = minPos.distanceTo(maxPos);
      for (GraphEdge e : graph.getAdjacent(elementVertex, ".*")) {
        if(!e.getRelationName().equals("Introduces")) {
          if(belongsToFeature(e.getSource(), featureVertex, graph)
              && belongsToFeature(e.getTarget(), featureVertex, graph)) {

            if(e.getSource() == e.getTarget()) {
              value = value + 1.0f;
            } else {
              value = value + (1.0f - (e.getLength() / diagonal));
            }
            count++;
          }
        }
      }
    }
    if(count > 0) {
      return Math.round(100.0f * (value / count));
    } else {
      return 100;
    }
  }

  public static int arExtended(GraphVertex featureVertex, GraphData graph) {

    LinkedList<GraphVertex> elements = new LinkedList<GraphVertex>();
    for(GraphEdge intrEdge : graph.getAdjacent(featureVertex, "Introduces")) {
      GraphVertex elementVertex;
      if(intrEdge.getSource() == featureVertex) {
        elementVertex = intrEdge.getTarget();
      } else {
        elementVertex = intrEdge.getSource();
      }
      elements.add(elementVertex);
    }

    if(elements.size() == 0) {
      return 100;
    } else {
      Position minPos = Position.min(graph.getVertices(), false);
      Position maxPos = Position.max(graph.getVertices(), false);
      float diagonal = minPos.distanceTo(maxPos);
      return Math.round(100.0f * (1.0f - (new RadiusOfGroup(elements).getAverageRadius() / diagonal)));
    }
  }

  public static int mrExtended(GraphVertex featureVertex, GraphData graph) {

    LinkedList<GraphVertex> elements = new LinkedList<GraphVertex>();
    for(GraphEdge intrEdge : graph.getAdjacent(featureVertex, "Introduces")) {
      GraphVertex elementVertex;
      if(intrEdge.getSource() == featureVertex) {
        elementVertex = intrEdge.getTarget();
      } else {
        elementVertex = intrEdge.getSource();
      }
      elements.add(elementVertex);
    }
    if(elements.size() == 0) {
      return 100;
    } else {
      Position minPos = Position.min(graph.getVertices(), false);
      Position maxPos = Position.max(graph.getVertices(), false);
      float diagonal = minPos.distanceTo(maxPos);
      return Math.round(100.0f * (1.0f - (new RadiusOfGroup(elements).getMaxRadius() / diagonal)));
    }
  }
}
